The present invention relates to polygon division methods and apparatus, and more particularly, to methods and apparatus for dividing a polygon having an arbitrary shape into triangles which are convex polygons having the simplest construction.
In a graphics display apparatus, it is strongly required that filling and displaying of polygons, each having an arbitrary shape, are to be performed at high speed. To satisfy the requirement, polygon division methods, each method being carried out prior to the filling and displaying, are proposed for dividing a concave polygon into plural triangles which are convex polygons having the simplest construction. The concave polygon has at least one apex having an interior angle greater than 180 degrees, while the convex polygon has no apex having an interior angle greater than 180 degrees.
Conventional polygon division methods are (I) a method for sequentially cutting triangles from a polygon by determining a concave apex as a reference apex, the concave apex having an interior angle greater than 180 degrees, (II) a method which uses jointly a triangle cutting method with a division method for dividing a polygon into two parts, (III) a trapezoid division method and (IV) a method for dividing a polygon at apexes using the trapezoid division method.
The method (I) is shown by a flowchart in FIG. 12.
In step SP1, concave apexes are extracted from all apexes of a polygon and a concave apex list is formed based on the extracted concave apexes. In step SP2, the concave apex list is searched to find the concave apex, then it is judged whether or not at least one concave apex exists. When it is judged in step SP2 that no concave apex exists, then in step SP3, triangles are sequentially cut from the polygon by determining an arbitrary convex apex as a reference apex. Thereafter, division of the polygon is finished. On the contrary, when it is judged in step SP2 that at least one concave apex exists, then in step SP4, an arbitrary concave apex is taken out from the concave apex list and is determined to be a reference apex P0. In step SP5, two apexes P1 and P2 are taken out from all the apexes of the polygon, the apexes P1 and P2 are sequential with respect to the reference apex P0 in a predetermined direction (for example, in a counter-clockwise direction). In step SP6, it is judged whether or not the apex P1 is a convex apex. When it is judged in step SP6 that the apex P1 is a convex apex, in step SPT, it is judged whether or not another apex exists in the interior of the triangle which is formed by the three apexes P0, P1 and P2. When it is judged in step SP7 that no apex exist in the interior of the triangle, in step SP8, the triangle is cut from the polygon. In step SP9, it is judged whether or not the concave apex has been varied to a convex apex following the cutting of the triangle. When it is judged in step SP9 that the concave apex has not been varied to a convex apex, the processing in step 5 is carried out again while maintaining the reference apex as it is. That is, the following apexes are taken out. On the contrary, when it is judged in step SP9 that the concave apex has been varied to a convex apex, in step SP10, the next concave apex is taken out from the concave apex list and is determined to be the reference apex P0. Then, the processing in step 5 is carried out again based on the newly determined reference apex.
When it is judged in step SP6 that the apex P1 is a concave apex, or it is judged in step SP7 that another apex exists in the interior of the triangle which is formed by the three apexes P0, P1 and P2, in step SP11, two apexes are taken out as the apexes P1 and P2 from all the apexes of the polygon, the apexes are sequential with respect to the reference apex P0 in the reverse direction (for example, in a clockwise direction). In step SP12, it is judged whether or not the newly taken out apex P1 is a convex apex. When it is judged in step SP12 that the apex P1 is a convex apex, in step SP13, it is judged whether or not another apex exists in the interior of the triangle which is formed by the three apexes P0, P1 and P2. When it is judged in step SP7 that no apex exists in the interior of the triangle, the processing in step SP8 is carried out. When it is judged in step SP12 that the apex P1 is a concave apex, or it is judged in step SP13 that another apex exists in the interior of the triangle which is formed by the three apexes P0, P1 and P2, in step SP14, the reference apex P0 is placed back to the end of the concave apex list. In step SP15, the next concave apex is taken out from the concave apex list, and is determined to be the new reference apex. Then, the processing in step SP5 is carried out again.
When the polygon having a shape illustrated in FIG. 13(A) is to be divided into plural triangles, only one concave apex is determined to be the reference apex. Plural triangles are sequentially cut from the polygon in a counter-clockwise direction. When a polygon having the shape illustrated in FIG. 13(B) is to be divided into plural triangles, plural triangles are sequentially cut from the polygon in a clockwise direction. Even when a polygon having the shape illustrated in FIG. 13(C) is to be divided into plural triangles, plural triangles are sequentially cut from the polygon in a clockwise direction.
The method (II) is shown by a flowchart in FIG. 14.
In step SP1, apexes of a polygon are sorted in a predetermined direction (for example, in a x-coordinate direction). In step SP2, it is judged whether or not another apex exists in the interior of a triangle formed by two edges which unite an apex existing at the end of the polygon (hereinafter referred to as end apex). When it is judged in step SP2 that no apex exists in the interior of the polygon, in step SP3, the triangle is cut from the polygon. Then, the processing in step SP1 is carried out again for the remaining apexes. On the contrary, when it is judged in step SP2 that another apex exists in the interior of the polygon, in step SP4, the polygon is divided into two divided polygons with respect to the end apex and an apex in the interior of the triangle and at the closest position with respect to the end apex. Then the series of operations are carried out for each divided polygon.
When the polygon having the shape illustrated in FIG. 15(A) is to be divided into plural triangles, triangles are sequentially cut from the polygon without dividing the polygon. When the polygon having the shape illustrated in FIG. 15(B) is to be divided into plural triangles, the polygon is divided into two divided polygons, then triangles are sequentially cut from each divided polygon in a manner similar to the polygon illustrated in FIG. 15(A).
The method (III) is shown by a flowchart in FIG. 16.
In step SP1, the apexes of a polygon are sorted in a predetermined direction (for example, in a y-coordinate direction). In step SP2, a list for pseudo-trapezoids is formed, a pseudo-trapezoid being determined by its upper edge and side edges and not being determined by its lower edge, and apexes of the polygon are classified into corresponding types. In step SP3, apexes are sequentially extracted in the sorted order. In step SP4, the extracted apex is recognized by its type and a corresponding pseudo-trapezoid is extracted. In step SP5, a trapezoid is formed by determining a scanning line as the lower edge, the scanning line passing through the extracted apex. In step SP6, the formed trapezoid is divided into two triangles by a diagonal line. In step SPT, a new pseudo-trapezoid is registered in the list, the new pseudo-trapezoid being formed by dividing the trapezoid. Then the series of operations are carried out again.
When a polygon having a shape illustrated in FIG. 17 is to be divided into plural triangles, the polygon is divided into plural trapezoids by the scanning lines, each scanning line passing through a corresponding apex, then each trapezoid is divided into two portions by a diagonal line so as to perform division of the polygon into plural triangles.
The method (IV) is shown by a flowchart in FIG. 18.
In step SP1, a pseudo-trapezoid which is to be divided from a polygon is searched at every apex, similarly to the method (III), and an apex list which stores apexes for generation of upper and lower edges of a trapezoid is formed. In step SP2, a pseudo-trapezoid list is searched at every apex in a predetermined direction (for example, in a clockwise direction) with respect to an apex of the polygon, and a pseudo-trapezoid is found, the apex of the pseudo-trapezoid for forming the upper edge being incident to the presently selected apex. In step SP3, it is judged whether or not a below apex corresponding to the apex forming the upper edge is a diagonal apex. The diagonal apex is used to express the relationship between the apex forming the upper edge and the apex forming the lower edge when both apexes exist on different edge lines of the polygon. When it is judged in step SP3 that the below apex is a diagonal apex, in step SP4, the polygon is divided into two portions by the diagonal apexes. In step SP5, it is judged whether or not all polygons including divided polygons are not impossibly divided. When it is judged in step SP3 that the below apex is not a diagonal apex, the processing in step SP2 is carried out for searching the following trapezoid list. When it is judged in step SP5 that at least one polygon can possibly be divided, the series of operations above-mentioned are carried out again. On the contrary, when it is judged in step SP5 that all polygons can not be divided, the divided polygon is a polygon which monotonously descends from the apex having the maximum y-coordinate value (hereinafter referred to as maximum apex) to the apex having the minimum y-coordinate value (hereinafter referred to as minimum apex) and in which the maximum apex and the minimum apex are neighhbouring one another (hereinafter the polygon is referred to as the uni-monotone polygon). In step SP6, three apexes (including the maximum apex and the minimum apex) are extracted in a predetermined direction (for example, in a clockwise direction) with respect to the maximum apex or the minimum apex, depending on whether the side edge formed by the maximum apex and the minimum apex is in the left side or the right side. In step SP7, it is judged whether or not the angle formed by the three apexes is a convex angle. When it is judged in step SP7 that the angle is a convex angle, in step SP8, the triangle formed by the three apexes is cut from the polygon. When it is judged in step SP7 that the angle is a concave angle, or the processing in step SP8 is carried out, in step SP9, three apexes are extracted with respect to the next apex. Then the processing in step SP6 is carried out again.
When the polygon having a partial shape illustrated in FIGS. 19(A) and 19(C) is to be divided into plural triangles, the polygon is divided into plural divided polygons by the diagonal apexes as are illustrated in FIGS. 19(B) and 19(D) to obtain plural uni-monotone polygons. The uni-monotone polygon is easily divided into triangles. FIGS. 20(A) through 20(E) are diagrams illustrating triangle division results obtained by the conventional methods, respectively. Wherein, FIG. 20(A) illustrates an original polygon, FIG. 20(B) illustrates the triangle division result by the method (I), FIG. 20(C) illustrates the triangle division result by the method (II), FIG. 20(D) illustrates the triangle division result by the method (III), and FIG. 20(E) illustrates the triangle division result by the method (IV).
The method (III) generates new apexes because the method generates trapezoids based on scanning lines which pass through corresponding apexes and divides each generated trapezoid into two triangles. Consequently, an obtained triangle is deformed when the calculation accuracy for generating a new apex is not improved to a sufficient accuracy. Also, depth values and color values may include errors in matching portions of neighbouring triangles and a vacant portion may be generated between neighbouring triangles.
The disadvantages above-mentioned do not arise in the methods (I), (II) and (IV) because these methods do not generate new apexes.
The disadvantage arises in the methods (I), (II), (III) and (IV) that operations are very complicated, quantities of software programs are large, and the quantity of data becomes large because of the quantity of information which is necessary for dividing a polygon into plural triangles. A polygon in which edges intersect one another (hereinafter referred to as a self-interference polygon) and a polygon in which plural apexes overlap one another at one point (hereinafter referred to as a degeneracy polygon) may not be divided into plural triangles properly.
More specifically, the methods (II) and (IV) sort apexes with respect to the x-coordinate or y-coordinate, then perform operations by determining the minimum apex as a starting apex. This is because both methods employ a prerequisite that the minimum apex must be a convex apex. When a polygon is a self-interference polygon as is illustrated in FIG. 21(A) for example, the minimum apex is a concave apex and the prerequisite is not satisfied. The methods (II) and (IV) are not applicable to self-interference polygons. When a polygon is a degeneracy polygon as is illustrated in FIG. 21(B), a convex apex and a concave apex overlap at a minimum point, thereby the minimum point may be recognized as a convex apex as is illustrated in FIG. 21(C) Or may be recognized as a concave apex as is illustrated in FIG. 21(D) depending on the sort result. This disadvantage is impossible to the solve essentially because there is no information showing the relationship between the apexes.
The method (I) is impossible to cut triangles from a polygon which is a self-interference polygon as is illustrated in FIG. 22(A) for example. When a polygon is a degeneracy polygon as is illustrated in FIG. 22(B), it is impossible to cut a triangle from the polygon under the condition that an overlap apex is recognized to exist in the interior of a triangle which is to be cut. Of course in this case, the triangle can be cut when an overlap apex is recognized to exist exterior to the triangle. When a polygon is a degeneracy polygon as is illustrated in FIG. 22(C), even though an overlap apex is recognized to exist at the exterior of a triangle which is to be cut, a triangle with its one edge illustrated by a dashed line in FIG. 22(C) is cut from the polygon. This makes it impossible to cut proper triangles.